/*
 * Copyright 2007-2008 by Matthias Buch-Kromann <mbk.isv@cbs.dk>.
 * 
 * This file is part of the Open-source Dependency Toolkit (OSDT),
 * see http://code.google.com/p/open-source-dependency-toolkit. 
 * 
 * The OSDT is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published
 * by the Free Software Foundation, either version 3 of the License,
 * or (at your option) any later version.
 *
 * The OSDT is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with the OSDT in the file COPYING and COPYING.LESSER. If not, see
 * http://www.gnu.org/licenses.
 */


package org.osdtsystem.graphs;

import java.io.IOException;
import java.io.StringWriter;
import org.osdtsystem.exceptions.FeatureNotFoundException;
import org.osdtsystem.exceptions.LayerNotFoundException;
import org.osdtsystem.exceptions.NodeNotFoundException;
import org.osdtsystem.exceptions.LocationNotFoundException;
import org.osdtsystem.exceptions.GraphException;
import org.osdtsystem.exceptions.OsdtSyntaxException;
import org.osdtsystem.functions.LocalFunction;
import org.osdtsystem.functions.SingletonFunction;
import org.osdtsystem.graphs.views.View;
import org.osdtsystem.values.Property;
import org.osdtsystem.values.NodeID;
import org.osdtsystem.values.Location;
import org.osdtsystem.values.LocalProperty;
import org.osdtsystem.values.Layer;
import org.osdtsystem.values.Feature;
import org.osdtsystem.values.EdgeID;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import org.osdtsystem.exceptions.FunctionRuntimeException;
import org.osdtsystem.exceptions.InconsistentGraphException;
import org.osdtsystem.exceptions.InvalidFunctionException;
import org.osdtsystem.exceptions.NonUniqueNameException;
import org.osdtsystem.functions.Function;
import org.osdtsystem.graphs.io.OsdtReader;
import org.osdtsystem.graphs.io.OsdtWriter;
import org.osdtsystem.graphs.views.ViewID;
import org.osdtsystem.utils.Helper;
import org.osdtsystem.utils.Storage;
import org.osdtsystem.values.LayeredFeature;
import static org.osdtsystem.values.Constants.*;

/**
 * A graph that is stored purely in memory. The graph may be a delta graph,
 * ie, a graph which specifies a modification of another graph (the base graph).
 * It is possible to assign features and functions to each node, edge, and layer in the 
 * graph. The graph keeps track of changes to all features and functions,
 * so that it can recompute function values with as little effort as possible.
 * @author Matthias Buch-Kromann <mbk.isv@cbs.dk>
 */
public class GraphEngine extends AbstractGraph {
    // Storage
    private Storage storage;
    
    // Node and edge layer fields
    private int nextlayer = 0;
    private final Map<Layer, String> layerNames;

    // Node fields
    private int nextnode = 0;
    private final Map<NodeID, Layer> nodes;
    private final Map<NodeID, List<EdgeID>> inEdges;
    private final Map<NodeID, List<EdgeID>> outEdges;
    private final Map<String, NodeID> namedNodes;
    
    // Edge fields
    private int nextedge = 0;
    private final Map<EdgeID, Layer> edges;
    private final Map<EdgeID, NodeID> inNode;
    private final Map<EdgeID, NodeID> outNode;
    
    // Delta graph fields
    final Graph baseGraph;
    private final Set<NodeID> deletedNodes;
    private final Set<EdgeID> deletedEdges;
    
    // Node and edge feature fields
    private final Map<Layer, Set<Feature>> layerFeatures;
    private final Map<Location, Map<Feature, Object>> featureValues;

    // Graph functions
    private final Map<String, Function> functionNames;
    private final Map<Layer, List<Function>> nodeFunctions;
    private final Map<Layer, List<Function>> edgeFunctions;

    // Function values
    private final Map<LocalFunction, Object> functionValues;
    private final Map<LocalProperty, Set<LocalFunction>> callers;
    private final LinkedHashSet<LocalFunction> outdatedLocalFunctions;
    private final Set<LocalFunction> functionComputationPath;
    private final GraphAccessor accessor;
    
    // Views
    private final LinkedHashMap<ViewID,View> views;
    private final Map<String,ViewID> namedViews;

            
    // Revision control
    private int revision = 0;
    
    // Operation counts
    private long countAddNode = 0;
    private long countRemoveNode = 0;
    private long countAddEdge = 0;
    private long countRemoveEdge = 0;
    private long countSetObject = 0;
    private long countSetFunctionValue = 0;
    
    // Settings
    private int initialInEdgesCapacity = 2;
    private int initialOutEdgesCapacity = 2;
    
    // Constructors
    public GraphEngine(final Graph base, final Storage storage) {
        // Storage
        this.storage = storage;
        
        // Delta graph fields
        baseGraph = base;
        if (base != null)
            base.update();

        // Create maps, lists, and sets
        layerNames = storage.<Layer,String>smallMap("layerNames");     
        
        // Node fields
        nodes = storage.<NodeID,Layer>bigMap("nodes");
        inEdges = storage.<NodeID,List<EdgeID>>bigMap("inEdges");
        outEdges = storage.<NodeID,List<EdgeID>>bigMap("outEdges");
        namedNodes = storage.<String,NodeID>smallMap("namedNodes");

        // Edge fields
        edges = storage.<EdgeID,Layer>bigMap("edges");
        inNode = storage.<EdgeID,NodeID>bigMap("inNode");
        outNode = storage.<EdgeID,NodeID>bigMap("outNode");

        // Node and edge feature fields
        layerFeatures = storage.<Layer,Set<Feature>>smallMap("layerFeatures");
        featureValues = storage.<Location, Map<Feature, Object>>bigMap("featureValues"); 
        
        // Local functions and function computations
        functionNames = storage.<String, Function>smallMap("functionNames");
        nodeFunctions = storage.<Layer, List<Function>>smallMap("nodeFunctions");
        edgeFunctions = storage.<Layer, List<Function>>smallMap("edgeFunctions");
        functionValues = storage.<LocalFunction, Object>bigMap("functionValues");
        callers = storage.<LocalProperty, Set<LocalFunction>>bigMap("localSuperfunctions");
        outdatedLocalFunctions = storage.<LocalFunction>smallLinkedHashSet("outdatedLocalFunction");
        functionComputationPath = storage.<LocalFunction>smallSet("functionComputationPath");
        accessor = new GraphAccessorEngine(this);
        
        // Views
        views = storage.<ViewID,View>smallLinkedHashMap("views");
        namedViews = storage.<String,ViewID>smallMap("namedViews");

        // Set base graph
        if (baseGraph == null) {
            deletedNodes = null;
            deletedEdges = null;
        } else {
            deletedNodes = storage.<NodeID>smallSet("deletedNodes");
            deletedEdges = storage.<EdgeID>smallSet("deletedEdges");
        }
        clearIDs();
    }
    
    /**
     * Creates normal graph stored in memory.
     */
    public GraphEngine() {
        this(null, defaultStorageFactory);
    }

    /**
     * Creates delta graph stored in memory with given base graph.
     * @param base the base graph that is modified by the delta graph
     */
    public GraphEngine(final Graph base) {
        this(base, defaultStorageFactory);
    }

    private void clearIDs() {
        // Reset next IDs
        if (baseGraph != null) {
            nextnode = baseGraph.nextNodeID();
            nextedge = baseGraph.nextEdgeID();
            nextlayer = baseGraph.nextLayerID();
        } else {
            nextnode = nextedge = nextlayer = 0;
        }
    }
    
    @Override
    public void clear() {
        // Reset IDs
        clearIDs();
        
        // Reset revision numbers
        revision = 0;
        
        // Reset counters
        countAddNode = countRemoveNode = countAddEdge = countRemoveEdge 
                = countSetObject = countSetFunctionValue = 0;
        
        // Clear layer fields
        layerNames.clear();
        
        // Clear node fields
        nodes.clear();
        inEdges.clear();
        outEdges.clear();
        namedNodes.clear();
        
        // Clear edge fields
        edges.clear();
        inNode.clear();
        outNode.clear();
        
        // Clear delta graph fields
        if (deletedNodes != null)
            deletedNodes.clear();
        if (deletedEdges != null)
            deletedEdges.clear();
        
        // Clear feature fields
        layerFeatures.clear();
        featureValues.clear();
        
        // Clear function fields
        nodeFunctions.clear();
        if (functionValues != null) 
            functionValues.clear();
        if (callers != null)
            callers.clear();
        if (outdatedLocalFunctions != null)
            outdatedLocalFunctions.clear();
    }
    
    // General graph methods

    @Override
    public int nextNodeID() {
        return nextnode;
    }
    
    @Override
    public int nextEdgeID() {
        return nextedge;
    }

    @Override
    public int nextLayerID() {
        return nextlayer;
    }
    
    // Layers
    @Override
    public Layer addLayer(final String name) {
        Layer id = new Layer(nextlayer++);
        layerNames.put(id, name);
        return id;
    }
    
    @Override
    public void removeLayer(final Layer layer) {
        ++revision;
        layerNames.remove(layer);
        for (NodeID node : nodes(layer))
            removeNode(node);
        for (EdgeID edge : edges(layer))
            removeEdge(edge);
    }

    @Override
    public List<Layer> layers() {
        // Return local node layer list if there is no base graph
        if (baseGraph == null)
            return Arrays.asList(layerNames.keySet().toArray(new Layer[0]));
        
        // There is a base graph: if local list is empty, return base graph's
        // node layer list
        if (layerNames.isEmpty())
            return baseGraph.layers();
        
        // Node layers are defined in both graphs: return union
        Set<Layer> layers = new HashSet<Layer>(baseGraph.layers());
        layers.addAll(layerNames.keySet());
        return Arrays.asList(layers.toArray(new Layer[0]));
    }

    @Override
    public String layerName(final Layer layer) {
        if (layerNames.containsKey(layer))
            return layerNames.get(layer);
        if (baseGraph != null) 
            return baseGraph.layerName(layer);
        return null;
    }

    @Override
    public Layer lookupLayer(final String name) {
        // Lookup layer locally
        for (Layer layer : layerNames.keySet())
            if (layerNames.get(layer).equals(name))
                return layer;
        
        // Lookup layer in base graph, if it exists
        if (baseGraph != null)
            return baseGraph.lookupLayer(name);
        
        // Throw exception because layer doesn't exist
        return null;
    }

    @Override
    public Layer layer(Location loc) {
        if (loc instanceof NodeID)
            return nodeLayer((NodeID) loc);
        else if (loc instanceof EdgeID)
            return edgeLayer((EdgeID) loc);
        else 
            return null;
    }

    @Override
    public boolean containsLayer(final Layer layer) {
        // Lookup layer locally
        if (layerNames.containsKey(layer))
            return true;
        
        // Lookup layer in base graph, if it exists
        if (baseGraph != null)
            return baseGraph.containsLayer(layer);
        
        // Return false
        return false;
    }
    
    // Nodes
    @Override
    public NodeID addNode(final Layer layer) throws LayerNotFoundException {
        // Check that node doesn't exist already
        if (! containsLayer(layer))
            throw new LayerNotFoundException("Cannot create node in non-existent layer " + layer);
        
        // The id is ok: increment node counter
        NodeID node = new NodeID(nextnode++);
        
        // Initialize node in graph
        ++revision;
        ++countAddNode;
        nodes.put(node, layer);
        outdateAddNode(node);
        
        // Return node
        return node;
    }

    @Override
    public NodeID addNode(final Layer layer, final String name) throws LayerNotFoundException {
        NodeID node = addNode(layer);
        try {
            setNodeName(node, name);
            return node;
        } catch (NodeNotFoundException ex) {
            throw new InconsistentGraphException("Graph inconsistency detected during addNode operation", ex);
        }
    }

    @Override
    public void removeNode(final NodeID node) {
        // Check whether node exists in the base graph or in this graph, 
        // and throw an exception if it doesn't
        boolean isInBaseGraph = baseGraph != null && baseGraph.containsNode(node);
        boolean isInLocalGraph = nodes.containsKey(node);
        if (! isInBaseGraph && ! isInLocalGraph)
            return;
        
        // Open graph revision
        ++countRemoveNode;
        ++revision;
        outdateRemoveNode(node);

        // Delete all edges at node in local graph
        for (EdgeID e : edges(node))
            removeEdge(e);

        // Then remove all features at node in local graph
        for (Feature f : features(node))
            removeFeature(node, f);

        // Delete node in local graph
        nodes.remove(node);
        inEdges.remove(node);
        outEdges.remove(node);

        // Record node as removed from base graph, if it exists in base graph
        if (isInBaseGraph)
            deletedNodes.add(node);
    }

    @Override
    public Layer nodeLayer(final NodeID node) {
        // First look for layer locally
        Layer layer = nodes.get(node);
        if (layer != null)
            return layer;
        
        // Then look for layer in base graph
        if (baseGraph != null)
            return baseGraph.nodeLayer(node);
        
        // Throw exception
        return null;
    }

    @Override
    public List<EdgeID> inEdges(final NodeID node) {
        // First look for edges locally
        List<EdgeID> in = inEdges.get(node);
        
        // Return local edge list if there is no base graph
        if (baseGraph == null)
            return (in != null)
                    ? Arrays.asList(in.toArray(new EdgeID[0]))
                    : Arrays.asList(new EdgeID[0]);
        
        // Base graph exists: Mix edge lists from the two graphs
        Set<EdgeID> edgeset = new HashSet<EdgeID>(baseGraph.inEdges(node));
        for (EdgeID e : deletedEdges)
            edgeset.remove(e);
        
        // Add edges from local graph
        if (in != null)
            edgeset.addAll(in);
        
        // Return resulting edge lset
        return Arrays.asList(edgeset.toArray(new EdgeID[0]));
    }
    
    @Override
    public List<EdgeID> outEdges(final NodeID node) {
        // First look for edges locally
        List<EdgeID> out = outEdges.get(node);
        
        // Return local edge list if there is no base graph
        if (baseGraph == null)
            return (out != null)
                    ? Arrays.asList(out.toArray(new EdgeID[0]))
                    : Arrays.asList(new EdgeID[0]);
        
        // Base graph exists: Mix edge lists from the two graphs
        Set<EdgeID> edgeset = new HashSet<EdgeID>(baseGraph.outEdges(node));
        for (EdgeID e : deletedEdges)
            edgeset.remove(e);
        
        // Add edges from local graph
        if (out != null)
            edgeset.addAll(out);
        
        // Return resulting edge lset
        return Arrays.asList(edgeset.toArray(new EdgeID[0]));
    }
    
    @Override
    public List<NodeID> nodes() {
        // Return local nodes if there is no baseGraph
        if (baseGraph == null)
            return Arrays.asList(nodes.keySet().toArray(new NodeID[0]));
        
        // There is a base graph: find union of nodes minus deleted ones
        Set<NodeID> nodeset = new HashSet<NodeID>(baseGraph.nodes());
        for (NodeID n : deletedNodes)
            nodeset.remove(n);
        nodeset.addAll(nodes.keySet());
        
        // Return resulting lset
        return Arrays.asList(nodeset.toArray(new NodeID[0]));
    }

    @Override
    public boolean containsNode(final NodeID node) {
        // Return true if node exists locally
        if (nodes.containsKey(node))
            return true;
        
        // Return true if node exists in base graph and hasn't been deleted
        if (baseGraph != null && baseGraph.containsNode(node) 
                && ! deletedNodes.contains(node))
            return true;
        
        // Otherwise return false
        return false;
    }

    @Override
    public void setNodeName(final NodeID node, final String name) 
            throws NodeNotFoundException {
        // Set named node
        if (containsNode(node))
            namedNodes.put(name, node);
        else
            throw new NodeNotFoundException("cannot assign name to non-existent node " + node);
    }
    
    @Override
    public NodeID lookupNamedNode(final String name) {
        // Try to retrieve node from local graph
        NodeID node = namedNodes.get(name);
        
        // Otherwise try to retrieve it from base graph
        if (node == null && baseGraph != null)
            node = baseGraph.lookupNamedNode(name);

        // Return node if it is non-null
        if (node != null)
            return node;
        
        // Otherwise throw exception
        return null;
    }

    // Edges
    @Override
    public EdgeID addEdge(final NodeID in, final NodeID out, final Layer layer) throws NodeNotFoundException, LayerNotFoundException  {
        // Check that in-node, out-node, and edge layer exist
        if (! containsNode(in))
            throw new NodeNotFoundException("non-existent node " + in);
        if (! containsNode(out))
            throw new NodeNotFoundException("non-existent node " + out);
        if (! containsLayer(layer))
            throw new LayerNotFoundException("non-existent layer " + layer);
        
        // Create edge
        EdgeID edge = new EdgeID(nextedge++);
        
        // Revise graph
        try { 
            // Open revision and record layer, in- and out-node for edge
            ++revision;
            ++countAddEdge;
            edges.put(edge, layer);
            inNode.put(edge, in);
            outNode.put(edge, out);
            
            // Add edge to out-edges
            if (! outEdges.containsKey(out))
                outEdges.put(out, new ArrayList<EdgeID>(initialOutEdgesCapacity));
            outEdges.get(out).add(edge);
            
            // Add edge to in-edges 
            if (! inEdges.containsKey(in))
                inEdges.put(in, new ArrayList<EdgeID>(initialInEdgesCapacity));
            inEdges.get(in).add(edge);
        } finally {
            // Close revision and warn other nodes about edge
            outdateAddEdge(edge);
        }
        
        // Return edge
        return edge;
    }
    
    @Override
    public void removeEdge(final EdgeID edge) {
        // Throw EdgeNotFoundException if the graph does not contain the given edge
        boolean isLocalEdge = edges.containsKey(edge);
        boolean isBaseEdge = (baseGraph != null) && baseGraph.containsEdge(edge);
        if (! (isBaseEdge || isLocalEdge)) 
            return;
        
        // The edge exists: delete it
        try {
            // Find in- and out-node
            NodeID innode = inNode(edge);
            NodeID outnode = outNode(edge);   
            
            // Open revision and outdate edge and edge nodes
            ++revision;
            ++countRemoveEdge;
            outdateRemoveEdge(edge);
            if (isLocalEdge) {
                // Edge is a local edge: delete edge features
                for (Feature f : features(edge))
                    removeFeature(edge, f);
                
                // Delete recorded layer, in- and out-node for edge
                edges.remove(edge);
                inNode.remove(edge);
                outNode.remove(edge);
                
                // Delete edge at in- and out-node
                outEdges.get(outnode).remove(edge);
                inEdges.get(innode).remove(edge);
            } else {
                // Edge is contained in base graph: overwrite all edge features 
                // with "null", and mark it as deleted in local graph
                for (Feature f : features(edge))
                    try {
                        if (featureValue(edge, f) != null)
                            setFeatureValue(edge, f, null);
                    } catch (FeatureNotFoundException e) {
                        // Ignore it
                    }
                
                // Mark edge as deleted
                deletedEdges.add(edge);
            }
        } catch (LocationNotFoundException ex) {
            throw new RuntimeException(
                    "Unexpectedly detected a runtime error, probably caused by concurrent modification",
                    ex);
        }
    }

    @Override
    public Layer edgeLayer(final EdgeID edge) {
        // Try to retrieve layer locally
        Layer layer = edges.get(edge);
        if (layer != null)
            return layer;
        
        // Try to retrieve layer from base graph
        if (baseGraph != null)
            return baseGraph.edgeLayer(edge);

        // Finally give up
        return null;
    }

    @Override
    public NodeID inNode(final EdgeID edge) {
        // Check for null
        if (edge == null)
            return null;
        
        // Try to retrieve in-node locally
        NodeID in = inNode.get(edge);
        if (in != null) 
            return in;
        
        // Try to retrieve node from basegraph;
        if (baseGraph != null)
            return baseGraph.inNode(edge);
        
        // Throw exception
        return null;
    }

    @Override
    public NodeID outNode(final EdgeID edge) {
        // Check for null edge
        if (edge == null)
            return null;
        
        // Try to retrieve out-node locally
        NodeID out = outNode.get(edge);
        if (out != null) 
            return out;
        
        // Try to retrieve node from basegraph;
        if (baseGraph != null)
            return baseGraph.outNode(edge);
        
        // Return null
        return null;
    }
    
    @Override
    public List<EdgeID> edges() {
        // Return local edge list if there is no base graph
        Set<EdgeID> edgesetl = edges.keySet();
        if (baseGraph == null)
            return Arrays.asList(edgesetl.toArray(new EdgeID[0]));
        
        // Base graph exists: Mix edge lists from the two graphs
        Set<EdgeID> edgeset = new HashSet<EdgeID>(baseGraph.edges());
        for (EdgeID e : deletedEdges)
            edgeset.remove(e);
        
        // Add edges from local graph
        edgeset.addAll(edgesetl);
        
        // Return resulting edge lset
        return Arrays.asList(edgeset.toArray(new EdgeID[0]));
    }
    
    @Override
    public boolean containsEdge(final EdgeID edge) {
        // Try to find edge locally
        if (edges.containsKey(edge))
            return true;
        
        // Try to find edge in base graph
        return (baseGraph != null && baseGraph.containsEdge(edge) 
                && ! deletedEdges.contains(edge));
    }
    
    @Override
    public boolean containsLocation(final Location location) {
        if (location instanceof EdgeID)
            return containsEdge((EdgeID) location);
        if (location instanceof NodeID) 
            return containsNode((NodeID) location);
        if (location instanceof Layer)
            return containsLayer((Layer) location);
        return false;
    }
    
    // Features
    @Override
    public void addLayerFeature(final Layer layer, final Feature feature) 
            throws LayerNotFoundException {
        // Check that layer is contained in graph
        if (! containsLayer(layer))
            throw new LayerNotFoundException("cannot add feature " + feature 
                    + " to non-existing layer " + layer);
        
        // Create local feature lset for layer if non-existent, copying feature
        // lset from base graph if possible
        if (! layerFeatures.containsKey(layer)) {
            if (baseGraph != null && baseGraph.containsLayer(layer))
                layerFeatures.put(layer, new HashSet<Feature>(baseGraph.features(layer)));
            else
                layerFeatures.put(layer, new HashSet<Feature>());
        }
        
        // Add feature to local feature lset
        layerFeatures.get(layer).add(feature);
    }
    
    @Override
    public List<Feature> features(final Layer layer) {
        return features(layer, false);
    }

    @Override
    public List<Feature> features(final Layer layer, final boolean includeInternalFeatures) {
        // Check whether layer is empty
        if (layer == null) 
            return Collections.emptyList();
        
        // Retrieve feature list locally, if possible
        if (layerFeatures.containsKey(layer)) {
            List<Feature> features = new ArrayList<Feature>();
            for (Feature feature : layerFeatures.get(layer)) {
                if (includeInternalFeatures || ! feature.internalFeature())
                    features.add(feature);
            }
            return Arrays.asList(features.toArray(new Feature[0]));
        }
        
        // Retrieve feature list from base graph, if possible
        if (baseGraph != null && baseGraph.containsLayer(layer))
            return baseGraph.features(layer, includeInternalFeatures);
        
        // Return empty list
        return Arrays.asList(new Feature[0]);
    }
    
    @Override
    public void removeFeature(final Location loc, final Feature feat) {
        try {
            ++revision;
            outdateProperty(loc, feat);
            if (baseGraph != null && baseGraph.featureValue(loc, feat) != null)
                setFeatureValue(loc, feat, null);
            else {
                Map<Feature,Object> submap = featureValues.get(loc);
                if (submap != null)
                    submap.remove(feat);
            }
            ++countSetObject;
        } catch (LocationNotFoundException ex) {
            // Ignore non-existent locations!
        } catch (FeatureNotFoundException ex) {
            // Ignore non-existent features!
        }
    }
    
    
    @Override
    public void setFeatureValue(final Location loc, final Feature feat, final Object val)
            throws LocationNotFoundException, FeatureNotFoundException {
        ++revision;

        // Check that location exists
        if (! containsLocation(loc))
            throw new LocationNotFoundException("Non-existent location " + loc);

        // Check that feature exists
        if (! permitsFeature(loc, feat))
            throw new FeatureNotFoundException("Feature " + feat + " not allowed at location " + loc);

        // Set feature
        outdateProperty(loc, feat);
        Map<Feature,Object> submap = featureValues.get(loc);
        if (submap == null) {
            submap = new HashMap<Feature, Object>();
            featureValues.put(loc, submap);
        }
        submap.put(feat, val);
    }
    
    
    @Override
    public Object featureValue(Location loc, Feature feat) {
        Map<Feature,Object> submap = featureValues.get(loc);
        if (submap != null && submap.containsKey(feat))
            return submap.get(feat);
        else if (baseGraph != null)
            return baseGraph.featureValue(loc, feat);
        else
            return null;
    }

    
    @Override
    public Feature decodeFeature(final Feature f) {
        return f;
    }

    @Override
    public Object decodeValue(final Object v) {
        return v;
    }

    @Override
    public boolean permitsFeature(final Location location, final Feature feature) {
        // All features are allowed at layers
        if (location instanceof Layer || feature.internalFeature())
            return true;
        
        // Find associated layer and layer features
        Layer layer = layer(location);
        Set<Feature> feats = layerFeatures.get(layer);
        if (feats != null)
            return feats.contains(feature);
        else if (baseGraph != null)
            return baseGraph.permitsFeature(layer, feature);
        else
            return false;
    }

    // Functions
    
    // TODO: Revision control
    @Override
    public int revision() {
        return revision;
    }

    private Object id() {
        return this;
    }
    
    @Override
    public void commitChangesToBase() {
        // Return immediately when no base graph
        if (baseGraph == null)
            return;

        // Mapper class: converting locations in this graph to locations in base graph
        class BaseMapper {
            Map<Layer,Layer> layerMap = new HashMap<Layer,Layer>();
            Map<NodeID,NodeID> nodeMap = new HashMap<NodeID,NodeID>();
            Map<EdgeID,EdgeID> edgeMap = new HashMap<EdgeID,EdgeID>();
            
            void lset(Layer l, Layer lb) {layerMap.put(l, lb);}
            void nset(NodeID n, NodeID nb) {nodeMap.put(n, nb);}
            void eset(EdgeID e, EdgeID eb) {edgeMap.put(e, eb);}
            
            Layer lmap(Layer l) {Layer lb = layerMap.get(l); return lb == null ? l : lb;}
            NodeID nmap(NodeID n) {NodeID nb = nodeMap.get(n); return nb == null ? n : nb;}
            EdgeID emap(EdgeID e) {EdgeID eb = edgeMap.get(e); return eb == null ? e : eb;}
            
            Location map(Location l) {
                if (l instanceof NodeID)
                    return nmap((NodeID) l);
                if (l instanceof EdgeID)
                    return emap((EdgeID) l);
                if (l instanceof Layer)
                    return lmap((Layer) l);
                return l;
            }
        }
        
        // Create new base mapper
        BaseMapper m = new BaseMapper();
       
        
        // Write changes to base graph
        try {
            // Delete all removed nodes and edges from base graph
            for (NodeID n : deletedNodes)
                baseGraph.removeNode(n);
            for (EdgeID e : deletedEdges)
                baseGraph.removeEdge(e);

            //  Copy all layers to base graph
            for (Layer l : Helper.sort(Arrays.asList(layerNames.keySet().toArray(new Layer[0]))))
                m.lset(l, baseGraph.addLayer(layerNames.get(l)));

            // Copy all nodes and named nodes to base graph
            for (NodeID n : Helper.sort(Arrays.asList(nodes.keySet().toArray(new NodeID[0]))))
                m.nset(n, baseGraph.addNode(m.lmap(nodes.get(n))));
            for (String name : namedNodes.keySet())
                baseGraph.setNodeName(m.nmap(namedNodes.get(name)), name);
            
            // Copy all edges to base graph
            for (EdgeID e : Helper.sort(Arrays.asList(edges.keySet().toArray(new EdgeID[0]))))
                m.eset(e, baseGraph.addEdge(m.nmap(inNode(e)), 
                    m.nmap(outNode(e)), m.lmap(layer(e))));
                
            // Copy all layer features to base graph
            for (Layer l : layerFeatures.keySet())
                for (Feature f : Helper.sort(Arrays.asList(layerFeatures.get(l).toArray(new Feature[0]))))
                    baseGraph.addLayerFeature(m.lmap(l), f);
                
            // Copy all feature values to base graph
            for (Location l : featureValues.keySet()) {
                Map<Feature, Object> submap = featureValues.get(l);
                for (Feature f : submap.keySet()) {
                    Location lb = m.map(l);
                    if (baseGraph.containsLocation(m.map(l)))
                        baseGraph.setFeatureValue(m.map(l), f, submap.get(f));
                }
            }
            
            // Copy layer functions to base graph
            for (Layer l : nodeFunctions.keySet()) {
                baseGraph.clearLayerFunctions(l);
                for (Function f : nodeFunctions.get(l))
                    baseGraph.addNodeFunction(l, null, f);
            }
        } catch (GraphException ex) {
            throw new RuntimeException("Unexpected inconsistency in graph. Aborting commit.", ex);
        } finally {
            // Clear this graph
            clear();
        }
    }
    
    @Override
    public void commitChangesToRoot() {
        // Return immediately if no base graph
        if (baseGraph == null)
            return;
        
        // Commit changes to base graph
        commitChangesToBase();
        
        // Recursively commit down to the root graph
        baseGraph.commitChangesToRoot();
    }

    @Override
    public List<Function> nodeFunctions(Layer layer) {
        if (nodeFunctions.containsKey(layer))
            return Collections.unmodifiableList(nodeFunctions.get(layer));
        else if (baseGraph != null)
            return baseGraph.nodeFunctions(layer);
        else 
            return Arrays.asList(new Function[0]);
    }

    @Override
    public List<Function> edgeFunctions(Layer layer) {
        if (edgeFunctions.containsKey(layer))
            return Collections.unmodifiableList(edgeFunctions.get(layer));
        else if (baseGraph != null)
            return baseGraph.edgeFunctions(layer);
        else 
            return Arrays.asList(new Function[0]);
    }

    @Override
    public void clearLayerFunctions(Layer layer) {
        nodeFunctions.remove(layer);
    }
    
    void addFunction(String name, Function function, 
                List<Function> layerFunctions) {
        // Check that function name doesn't exist already
        if (lookupFunction(name) != null) 
            throw new FunctionRuntimeException("Illegal function name: " +
                    "graph already contains a function named " + name);

        // Store function under function name
        functionNames.put(name, function);
        
        // Add new function to list
        layerFunctions.add(function);
    }

    @Override
    public void addEdgeFunction(Layer layer, String name, Function function) {
        // Create list of layer functions, copying it from base if necessary
        List<Function> list = edgeFunctions.get(layer);
        if (list == null) {
            if (baseGraph != null)
                list = new ArrayList(baseGraph.edgeFunctions(layer));
            else
                list = new ArrayList();
            edgeFunctions.put(layer, list);
        }
        
        // Add function to layer
        addFunction(name, function, list);
    }

    @Override
    public void addNodeFunction(Layer layer, String name, Function function) 
            throws InvalidFunctionException {
        // Check that layer has associated function list, and copy it from base
        // layer if not
        List<Function> list = nodeFunctions.get(layer);
        if (list == null) {
            if (baseGraph != null)
                list = new ArrayList(baseGraph.nodeFunctions(layer));
            else 
                list = new ArrayList<Function>();
            nodeFunctions.put(layer, list);
        }

        // Now add function to list of layer functions
        addFunction(name, function, list);
    }
    
    
    @Override
    public Function lookupFunction(String name) {
        if (functionNames.containsKey(name))
            return functionNames.get(name);
        else if (baseGraph != null)
            return baseGraph.lookupFunction(name);
        else
            return null;
    }
    

    @Override
    public void removeNodeFunction(Layer layer, Function f) {
        List<Function> layerFunctions = nodeFunctions.get(layer);
        if (layerFunctions != null)
            layerFunctions.remove(f);
    }


    @Override
    public void removeEdgeFunction(Layer layer, Function f) {
        List<Function> layerFunctions = edgeFunctions.get(layer);
        if (layerFunctions != null)
            layerFunctions.remove(f);
    }


    
    @Override
    public boolean descendsFrom(Graph ancestor) {
        // Return true if this graph equals the ancestor
        if (this == ancestor)
            return true;
        
        // Pass on the question to the base graph if it exists
        if (baseGraph != null)
            return baseGraph.descendsFrom(ancestor);
        
        // Otherwise return false
        return false;
    }

    @Override
    public ViewID addView(View view, String name) throws NonUniqueNameException {
        // Fail if view name already exists in graph
        ViewID id = new ViewID(name);
        if (namedViews.containsKey(name)) 
            throw new NonUniqueNameException("Trying to add view with existing view name " + name);

        // Create new view and return id
        views.put(id, view);
        namedViews.put(name, id);
        return id;
    }

    @Override
    public View view(ViewID id) {
        View view = views.get(id);
        
        // If view doesn't exist here, look in base and copy it if possible
        if (view == null && baseGraph != null) {
            View baseView = baseGraph.view(id);
            if (baseView != null) {
                view = baseView.copy();
                view.setGraph(this);
            }
        }
        
        // Return view
        return view;
    }
    
    @Override
    public ViewID viewID(String name) {
        ViewID viewID = new ViewID(name);
        return (view(viewID) != null) ? viewID : null;
    }
    
    @Override
    public ViewID viewID(View view) {
        // Find view ID locally
        for (Entry<ViewID,View> entry : views.entrySet()) {
            if (entry.getValue().equals(view))
                return entry.getKey();
        }
        
        // Try to find it in base graph
        if (baseGraph != null)
            return baseGraph.viewID(view);
        
        // Finally give up and return null
        return null;
    }
    
    @Override
    public List<ViewID> views() {
        List<ViewID> list = new ArrayList<ViewID>();
        if (baseGraph != null)
            list.addAll(baseGraph.views());
        list.addAll(views.keySet());
        return Arrays.asList(list.toArray(new ViewID[0]));
    }

    @Deprecated
    public String toOSDT() {
        return toOSDT(false);
    }
    
    /**
     * 
     * @param internal
     * @return
     * @deprecated
     */
    @Deprecated
    public String toOSDT(boolean internal) {
        StringWriter writer = new StringWriter();
        try {
            OsdtWriter osdt = new OsdtWriter(writer, this);
        } catch (IOException ex) {
            return null;
        }
        return writer.toString();
    }

    @Deprecated
    public Graph fromOSDT(String osdt) throws OsdtSyntaxException {
        OsdtReader reader = new OsdtReader(osdt, this);
        reader.next();
        return this;
    }

    @Override
    public String viewName(ViewID id) {
        // Look locally first
        for (String name : namedViews.keySet()) {
            if (namedViews.get(name).equals(id))
                return name;
        }
        
        // Alternatively, look in base graph
        if (baseGraph != null)
            return baseGraph.viewName(id);
        
        // Otherwise give up
        return null;
    }

    @Override
    public String viewName(View view) {
        return viewName(viewID(view));
    }

    @Override
    public void addCaller(LocalFunction<?,?> caller, LocalProperty<?,?> property) {
        // Abort if no caller
        if (caller == null)
            return;

        // Make sure that local super functions recorded for property
        if (! callers.containsKey(property)) {
            callers.put(property, storage.<LocalFunction>smallSet(""));
        }

        // Add caller as listener
        callers.get(property).add(caller);
    }

    @Override
    public void addCaller(LocalFunction<?, ?> caller, Location location, Feature feature) {
        if (caller == null)
            return;
        addCaller(caller, new LocalProperty(location, feature));
    }

    @Override
    public void addCaller(LocalFunction<?, ?> caller, Location location, Layer layer,
            Feature feature) {
        if (caller == null)
            return;
        addCaller(caller, new LocalProperty(location, new LayeredFeature(layer, feature)));
    }


    @Override
    public void outdateProperty(Location location, Property property) {
        outdateParents(new LocalProperty(location, property));
    }

    private void outdateParents(LocalProperty localProperty) {
        // Find parent functions
        Set<LocalFunction> parents = callers.get(localProperty);
        if (parents != null) {
            for (LocalFunction parent : parents)
                // Recursively outdate all parent functions
                outdateFunction(parent);

            // Now remove all parent functions as listeners on this site (they have to
            // add themselves as parents again when they update)
            parents.clear();
        }
    }

    public void outdateFunction(Location location, Function function) {
        outdateFunction(new LocalFunction(location, function));
    }

    public void outdateFunction(LocalFunction localFunction) {
        outdateParents(localFunction);
        outdatedLocalFunctions.add(localFunction);
    }

    private void outdateAddNode(NodeID node) {
        // Outdate each function at the node, evaluation takes care of rest
        for (Function f : nodeFunctions(nodeLayer(node))) {
            outdateFunction(node, f);
        }
    }

    private void outdateRemoveNode(NodeID node) {
        // Same as outdateAddNode: we only need to outdate the functions at the node,
        // since edge deletions are outdated by outdateRemoveEdge.
        outdateProperty(node, NODE);
        outdateAddNode(node);
    }

    private void outdateAddEdge(EdgeID edge) {
        // Outdate the neighbourhood of the in- and out-node on the edge
        Layer layer = layer(edge);
        outdateProperty(inNode(edge), new LayeredFeature(layer, INEDGES));
        outdateProperty(outNode(edge), new LayeredFeature(layer, OUTEDGES));

        // Outdate each function at the edge
        for (Function f : edgeFunctions(layer))
                outdateFunction(edge, f);
    }

    private void outdateRemoveEdge(EdgeID edge) {
        // Same as outdateAddEdge
        outdateProperty(edge, EDGE);
        outdateAddEdge(edge);
    }

    @Override
    public Set<LocalFunction> callers(LocalProperty called) {
        // First try to look locally
        Set<LocalFunction> callersSet = callers.get(called);
        if (callersSet != null)
            return callersSet;

        // Then look in basegraph
        if (baseGraph != null)
            return baseGraph.callers(called);

        // Otherwise return null
        return null;
    }

    private boolean functionalDependency(Function function, Function subfunction) {
        // TODO: Check whether functions depend on each other
        return true;
    }

    @Override
    public void update() {
        while (! outdatedLocalFunctions.isEmpty()) {
            LocalFunction[] localFunctions = outdatedLocalFunctions.toArray(new LocalFunction[0]);
            for (LocalFunction lf : localFunctions) {
                functionValue(lf, accessor);
                outdatedLocalFunctions.remove(lf);
            }
        }
    }

    @Override
    public Object cachedFunctionValue(LocalFunction<?, Function<?>> called) {
        // Check whether caching is turned on
        if (functionValues == null)
            return null;
        
        // First look locally
        if (functionValues.containsKey(called))
            return functionValues.get(called);
        
        // Then check in base graph, if it exists
        if (baseGraph != null)
            return baseGraph.cachedFunctionValue(called);
        
        // Otherwise return null
        return null;
    }

    @Override
    public Object functionValue(Location location, String name) {
        return functionValue(location, name, this.accessor);
    }

    @Override
    public Object functionValue(Location location, String name, GraphAccessor accessor) {
        Function function = lookupFunction(name);
        if (function != null) {
            return functionValue(new LocalFunction(location, function), accessor);
        } else {
            return null;
        }
    }

    private Object functionValue(LocalFunction called, GraphAccessor accessor) {
        // Detect cyclic function computation
        if (functionComputationPath.contains(called)) {
            throw new FunctionRuntimeException("Cyclic function dependency in computation of function " + called);
        }
        functionComputationPath.add(called);

        // Check whether function is outdated
        if (! outdatedLocalFunctions.contains(called)) {
            // Return cached function value if it exists
            Object cached = cachedFunctionValue(called);
            if (cached != null)
                return cached;
        }

        // Recompute function value
        Object value = called.function().functionValue(called, null, accessor);

        // Mark local function as updated
        outdatedLocalFunctions.remove(called);
        functionComputationPath.remove(called);

        // Return function value
        return value;
    }

    @Deprecated
    public <V> List<V> functionValue(Location location, Function<V> function) {
        return function.functionValue(location, accessor);
    }
}


